1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <cstdio>
#include <cstring>
const int maxn = 255;
using namespace std;
double p[maxn], d[maxn], pow[maxn][maxn], f[maxn][maxn];
int min(int a, int b){
return a < b ? a : b;
}
int T, n, r;
int main(){
scanf("%d", &T);
while (T--){
memset(pow, 0, sizeof pow); memset(f, 0, sizeof f);
scanf("%d%d", &n, &r);
for (int i = 1; i <= n; i++){
scanf("%lf%lf", p + i, d + i);
pow[i][0] = 1;
for (int j = 1; j <= r; j++) pow[i][j] = pow[i][j - 1] * (1 - p[i]);
}
f[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= min(i, r); j++){
f[i][j] = f[i - 1][j] * pow[i][r - j];
if (j != 0) f[i][j] += f[i - 1][j - 1] * (1 - pow[i][r - j + 1]);
}
}
double ans = 0;
for (int i = 1; i <= n; i++){
double P = 0;
for (int j = 0; j <= min(i, r); j++)
P += f[i - 1][j] * (1 - pow[i][r - j]);
ans += P * d[i];
}
printf("%.10lf\n", ans);
}
return 0;
}
|